//: [Previous](@previous)
import Foundation

/*:
 你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋 ( K 至少为 1)。现在确定这栋楼存在楼层 0 <= F <= N ，在这层楼将鸡 蛋扔下去，鸡蛋恰好没摔碎(高于 F 的楼层都会碎，低于 F 的楼层都不 会碎)。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层
 F 呢?

 1,N=0
 N,K=1
 */

var memo: [String: Int] = [:]
func superEggDrop(_ K: Int, _ N: Int) -> Int {
    return dp(K, N)
}

func dp(_ K: Int, _ N: Int) -> Int {
    if  K == 1 {
        return N
    }
    if N == 0 {
        return 0
    }
    if let num = memo["\(K)_\(N)"] {
        return num
    }

    var res = Int.max
    for i in 1...N {
        res = min(
            res,
            max(dp(K, N-i), dp(K-1, i-1)) + 1
        )
    }
    memo["\(K)_\(N)"] = res
    return res
}

print(superEggDrop(1, 2))
print(superEggDrop(2, 6))
print(superEggDrop(3, 14))

/*:
 二分查找
 */
var memo2: [String: Int] = [:]
func dp2(_ K: Int, _ N: Int) -> Int {
    if  K == 1 {
        return N
    }
    if N == 0 {
        return 0
    }
    if let num = memo2["\(K)_\(N)"] {
        return num
    }

    var res = Int.max
    // 用二分搜索代替线性搜索
    var l = 1, r = N
    while l <= r {
        let mid = (l + r) / 2
        let broken = dp2(K - 1, mid - 1) //会碎
        let not_broken = dp2(K, N - mid) //不会碎

        if broken > not_broken {
            r = mid - 1
            res = min(res, broken + 1)
        } else {
            l = mid + 1
            res = min(res, not_broken + 1)
        }
    }

    memo2["\(K)_\(N)"] = res
    return res
}

print(dp2(1, 2))
print(dp2(2, 6))
print(dp2(3, 14))

/*:
 高楼扔鸡蛋 进阶 重新定义状态转移方程
 dp[k][m] = n
 # 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
 # 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
 # 比如说 dp[1][7] = 7 表示:
 # 现在有 1 个鸡蛋，允许你扔 7 次;
 # 这个状态下最多给你 7 层楼，
 # 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎 # (一层一层线性探查嘛)
 */

var memo3: [String: Int] = [:]
func dp3(_ K: Int, _ N: Int) -> Int {
    var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: N+1), count: K+1)
    // base case:
    // dp[0][..] = 0
    // dp[..][0] = 0
    var m = 0
    while dp[K][m] < N {
        m += 1
        for k in 1...K {
            dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
        }
    }
    print(dp)
    return m
}
print("-----3--------")
//print(dp3(1, 2))
print(dp3(2, 6))
//print(dp3(3, 14))

//: [Next](@next)
